#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/11 11:39
# @USER    : Shengji He
# @File    : FindFLPosArraySorted.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        """
        Given an array of integers nums sorted in ascending order, find the starting and ending position of a given
        target value.

        Your algorithm's runtime complexity must be in the order of O(log n).

        If the target is not found in the array, return [-1, -1].

        Example 1:

            Input: nums = [5,7,7,8,8,10], target = 8

            Output: [3,4]
        Example 2:

            Input: nums = [5,7,7,8,8,10], target = 6

            Output: [-1,-1]

        :param nums: List[int]
        :param target: int
        :return: List[int]
        """
        ans = [-1, -1]
        if not nums:
            return ans
        if target < nums[0] or target > nums[-1]:
            return ans
        ls, rs = 0, len(nums) - 1
        while rs - ls >= -1:
            if target == nums[ls]:
                if ans[0] == -1 or ls < ans[0]:
                    ans[0] = ls
                else:
                    if ans[1] > ls:
                        break
                    else:
                        ans[1] = ls
                ls += 1
            elif target > nums[ls]:
                ls += 1
            else:
                if ans[0] != -1:
                    ans[1] = ls - 1
                break

            if target == nums[rs]:
                if ans[1] == -1 or rs > ans[1]:
                    ans[1] = rs
                else:
                    if -1 < ans[0] < rs:
                        break
                    else:
                        ans[0] = rs
                rs -= 1
            elif target < nums[rs]:
                rs -= 1
            else:
                if ans[1] != -1:
                    ans[0] = rs + 1
                break
        return ans


if __name__ == '__main__':
    S = Solution()
    # nums = [1, 2, 3]
    # nums = [1, 2]
    # target = 1
    nums = [5, 7, 7, 8, 8, 10]
    # target = 8
    target = 6
    print(S.searchRange(nums, target))
    print('done')
